#define _CRT_SECURE_NO_WARNINGS	

#include<stdio.h>
#include<stdlib.h>

void Merge_Sort(int arr[], int left, int right)
{
    if (right - left <= 1)
        return;

    int mid = left + (right - left) / 2;
    Merge_Sort(arr, left, mid);
    Merge_Sort(arr, mid, right);

    int i = left, j = mid, k = 0;

    int* tmp = (int*)malloc(sizeof(int) * (right - left));

    while (i < mid && j < right)
    {
        if (arr[i] <= arr[j])
            tmp[k++] = arr[i++];
        else
            tmp[k++] = arr[j++];
    }

    while (i < mid)
        tmp[k++] = arr[i++];
    while (j < right)
        tmp[k++] = arr[j++];

    k = 0; 
    i = left;
    for (; i < right; i++)
        arr[i] = tmp[k++];
    free(tmp);
}

int main()
{
    int arr[8] = { 4,3,2,1,9,8,7,6 };
    Merge_Sort(arr, 0, 8);
    for (int i = 0; i < 8; i++)
        printf("%d ", arr[i]);
    return 0;
}